import java.util.*;
public class test {
    // leetcode 334.递增的三元子序列
    // 1. 动态规划(超时) -> O(n^2)
    // 类似(最长递增子序列)
    public boolean increasingTriplet1(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp,1);//默认最短为1
        for(int i = 1;i <= n;i++){
            for(int j = 1;j < i;j++){
                if(nums[i - 1] > nums[j - 1]){
                    dp[i] = Math.max(dp[j] + 1,dp[i]);
                }
            }
            if(dp[i] >= 3){
                return true;
            }
        }
        return false;
    }
    // 2. 动态规划 + 贪心 -> O(Nlogn)
    public boolean increasingTriplet2(int[] nums) {
        long INF = (long)Integer.MIN_VALUE - 1;
        int n = nums.length;
        long[] arr = new long[n + 1];
        // 默认为暂时没有找到该长度
        Arrays.fill(arr,INF);
        arr[1] = nums[0];
        int len = 1;
        for(int i = 2;i <= n;i++){
            int temp = nums[i - 1];
            int left = 0;
            int right = i;
            // 最右的二分查找
            while(left < right){
                int mid = left + (right - left + 1) / 2;
                if(arr[mid] == INF || arr[mid] >= temp){
                    right = mid - 1;
                }else {
                    left = mid;
                }
            }
            if(arr[left + 1] == INF){
                arr[left + 1] = temp;
                len++;
                if(len >= 3){
                    return true;
                }
            }else {
                arr[left + 1] = Math.min(arr[left + 1],temp);
            }
        }
        return false;
    }
    // 3. 贪心 -> O(n)
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        long INF = (long)Integer.MIN_VALUE - 1;
        int len = 1;
        //分别代表三元组中的第1,2,3个数
        long[] arr = new long[3];
        Arrays.fill(arr,INF);
        arr[0] = nums[0];
        out:for(int i = 1;i < n;i++){
            int temp = nums[i];
            for(int j = 0;j < 3;j++){
                // 当前位置存在,并且该元素小于以存储元素
                if(arr[j] != INF){
                    if(temp < arr[j]){
                        arr[j] = temp;
                        break;
                    }else if(temp > arr[j]){
                        continue;
                    }
                    continue out;
                }else if(arr[j] == INF){
                    arr[j] = temp;
                    len++;
                    if(len >= 3){
                        return true;
                    }
                    break;
                }
            }
        }
        return false;
    }
    // leetcode 674.最长连续递增序列
    public int findLengthOfLCIS(int[] nums) {
        int max = 1;
        int newmax = 1;
        int n = nums.length;
        for(int i = 1;i < n;i++){
            if(nums[i] > nums[i - 1]){
                newmax++;
            }else {
                max = Math.max(max,newmax);
                newmax = 1;
            }
        }
        max = Math.max(max,newmax);
        return max;
    }
    // leetcode 1005.K次取反后最大化的数组和
    public int largestSumAfterKNegations(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int n = nums.length;
        int sum = 0;
        for(int i = 0;i < n;i++){
            sum += nums[i];
            queue.add(nums[i]);
        }
        while(k-- > 0){
            int temp = queue.poll();
            sum -= 2 * temp;
            temp = -temp;
            queue.add(temp);
        }
        return sum;
    }
}
